Transcript Stack

2005MEE Software
Engineering
Lecture 7 –Stacks, Queues
Stack ADT


A stack is a last in first out (LIFO) data structure,
commonly used in many applications
All operations occur at the top of the stack
– not possible to access elements which are not on top

Operations
–
–
–
–
–
–
create stack
push : add an object to the top of the stack
top : view the top element of the stack (do not remove)
pop : take the top element from the stack
empty : clear the stack
size : return the current size of the stack
stack.h
Note that again, the data structure is incomplete,
meaning that the user can only access the stack
using these functions.
typedef struct stack_s *Stack ;
Stack createStack ( void ) ;
int push ( Stack s, void *newdata ) ;
void *top ( Stack s ) ;
void *pop ( Stack s ) ;
void emptyStack ( Stack s ) ;
int stackSize ( Stack s ) ;
Stack Implementation


Can be done in a number of ways
Array implementation
– must ‘grow’ to accommodate more data as required
– no shuffling of data required as all operations occur at end
of array

Linked list implementation
– very efficient as all operations occur at front of list,
meaning no traversal required
– grows naturally to contain unlimited amount of data

Same header file can be used for each
implementation!
– different implementation .c files
Stack – List
Implementation

Very similar to linked list implementation
– define two structures for header and nodes
– no need to store last node as all operations
occur at front
– insertion is always done at front so much simpler
– removal is always done at front so much simpler

See stack_list.c for exact implementation
Stack List Complexity

push, pop, top are all O(1)
– insertion at start of list and thus no
traversal required

size() could required a full traversal
– however having a ‘size’ variable means
this is not necessary, so still O(1)

empty() required full traversal to
remove memory of each node, so O(n)
Stack – Array
Implementation



Uses an array of void pointers to store data
Must be of some defined size to start with
Must transparently ‘grow’ this array as it
becomes full
–
–
–
–

create a new, larger array
copy all data across
free old array
new array becomes the data for the stack
See stack_array.c for exact implementation
Stack Array Complexity

push, pop, and top are usually O(1)
– all operations at end of array, so no shuffling or traversal
required
– HOWEVER: increasing size of array requires copying each
element, so O(n)



size() is O(1) as size field must be kept
empty() is again O(n) since each element must be removed –
for simple data types this is not necessary so O(1)
Note that array implementation uses less memory than list
implementation when full
– no node structures to store for each element
– however more memory when empty, as array is still taking up
space
– memory is also not unallocated when stack shrinks, so this can
cause wastage too..
Applications of Stacks

Stacks are used in many areas of
computing:
– hardware: most processors have a stack register
– storage for local variables which are ‘popped’ off
stack when function is complete
– language processing: elements are pushed onto
stack and processed as they are removed

Many real world applications are also
modeled well by stacks…
Queues



A queue is a first in first out (FIFO)
data structure
All insertions are at one end, removals
at other
Applications:
– instruction queues, scheduling
– data communication, buffers
– system modelling
Queues

Conceptual diagram:
rear
13
Data in


front
21
-56
1
9
6
Data out
All data enters queue at the rear
All data leaves queue from the front
Queue Operations






create queue
add : add an item to the end of the queue
front : get the item at the front of the
queue without removing it
next : get the item at the front of the queue
and remove it
empty : empty the queue
size : return the size of the queue
queue.h
typedef struct queue_struct *Queue ;
Queue queue_create() ;
int queue_add ( Queue q, int item ) ;
int queue_next ( Queue q ) ;
int queue_first ( Queue q ) ;
int queue_size ( Queue q ) ;
int queue_empty ( Queue q ) ;
int queue_destroy ( Queue q ) ;
Queue Implementation

A queue is most easily implemented using a linked
list structure
– either pointers to both the first and last elements
– or a circularly linked list (last element links back to first)

Array implementation uses circular array
– requires indices of front and rear of queue to be stored
– queue may ‘wrap’ around from end of array to beginning
– algorithm is straightforward, however code is somewhat
complex
Queue – Linked List

Circularly linked list is an interesting data
structure
– header node contains reference to only one
node – the REAR of the queue
– front of the queue is always the very NEXT node
– when only one node, it is linked to itself!

An elegant data structure, but requires care
when coding
– a number of ‘special cases’
– easy to lose nodes, or enter infinite loops
Queue – Linked List
size
rear
rear of queue
6
13
head of
queue
21
6
-56
1
9
Adding a Node (10)
size
rear
10
6
13
21
6
-56
1
9
Adding a Node

Basic algorithm:
– newnode->next = rear->next
– rear->next = newnode
– rear = newnode

Special case – empty queue:
– must link newnode to itself
– newnode->next = newnode
– rear = newnode
Removing a Value
size
rear
6
13
21
6
-56
1
9
Removing a Value

Basic algorithm:
–
–
–
–
–
–

temp = rear->next
data = temp->data
rear->next = rear->next->next
deallocate temp
return data
NOTE: value of ‘rear’ is unchanged (as expected)
Special case – only one node:
– rear = NULL
Calculating Size

Simple method:
– store size in header node, return
– update for every add/next operation

Complex method:
– iterate around loop until back to first
node
– NOTE: must use do..while loop to ensure
loop does not terminate immediately
Array Implementation

Simple implementation:
– front of queue is always index 0
– adding elements always at rear (identical to
stack implementation)
– removing elements requires shuffle down


Inefficient implementation as next() is O(n)
Using a circular array overcomes this
problem
– array ‘wraps’ around at end back to beginning
– both front and rear indices move as queue
changes
Queue Array
front = 2
6
rear = 7
9
1
-56
21
13
OR
-56
21
rear = 2
front = 7
13
6
9
1
Adding a Value

Basic algorithm:
– rear = ( rear + 1 ) % array_size
– add new value at ‘rear’

Special cases:
– array is full: create new, larger array and
repopulate from start
– queue is empty: store new element at
index 0, set front and rear to 0
Removing a Value

Basic algorithm:
– get value at position ‘front’
– front = ( front + 1 ) % array_size
– return value

Special cases:
– queue is empty: return error code
– last element: ?