Data Structures and Algorithms/Stacks and Queues
Stacks and Queues are both special-purpose lists, that restrict how the application can access data. This is done so that the structures can optimize themselves for speed. Both data structures are very simple, can be implemented with both linked-lists and vectors, and are used in many different programming applications.
Stacks
[edit | edit source]A Stack is a data type that only allows users to access the newest member of the list. It is analogous to a stack of paper, where you add and remove paper from the top, but never look at the papers below it.
A typical Stack implementation supports 3 operations: Push(), Pop(), and Top().
- Push() will add an item to the end of the list. This takes constant time.
- Pop() will remove the item at the end of the list. This takes constant time.
- Top() will return the value of the item at the top.
All operations on a stack happen in constant time, because no matter what, the stack is always working with the top-most value, and the stack always knows exactly where that is. This is the main reason why Stacks are so amazingly fast.
Stacks are also fairly simple to program. Here is a sample implementation in C:
/* Note: this Stack will store int's.*/
typedef struct {
int *array;
unsigned int index;
unsigned int max_size;
} Stack;
void Stack_push(Stack *in, int value) {
if( in->index+1 >= in->max_size ) {
in->max_size *= 2;
in->array = realloc(in->array, sizeof(int) * in->max_size);
}
in->array[in->index++] = value;
}
int Stack_pop(Stack *in) {
if( in->index != 0 )
in->index--;
return in->array[in->index];
}
int Stack_top(Stack *in) {
if(in->index==0)
return 0;
return in->array[in->index-1];
}
The code begins with the structure definition, which is fairly straight-forward. It contains a pointer to the data array, an integer that stores the index of the next insertion, and an integer that tells how many entries the array can store.
The push() procedure will reallocate the array if it does not have enough room for the new value. Then, the new value is stored into the data array, and the index is incremented.
The pop() function will decrement the index, and returns the value that just got popped.
The top() function will return an arbitrary value (0 in this case) if the Stack is empty, and returns the most-recent value otherwise.
Queues
[edit | edit source]A Queue is a data structure where you can only access the oldest item in the list. It is analogous to a line in the grocery store, where many people may be in the line, but the person in the front gets serviced first.
A typical Queue implementation has 3 operations, which are similar to the functions in Stacks. They are: enqueue(), dequeue(), and Front().
- Enqueue() will add an item to the end of the list. This takes constant time.
- Dequeue() will remove an item from the beginning of the list. This takes constant time.
- Front() will return the value of front-most item.
Queues, like Stacks, are very fast because all of the operations are simple, and constant-time.
I will provide a sample implementation in C. However, this code will produce a Queue that cannot resize when it runs out of room.
/* Note: this Queue will store int's.*/
typedef struct {
int *array;
unsigned int front;
unsigned int end;
unsigned int current_size;
unsigned int max_size;
} Queue;
void Queue_enqueue(Queue *in, int value) {
if( ++in->current_size > in->max_size ) {
/* We have overflowed. We just return here, but it would be best
* to somehow signal this failure to the rest of the program. */
in->current_size--;
return;
}
in->array[in->end] = value;
in->end = (in->end+1) % in->max_size;
}
int Queue_dequeue(Queue *in) {
int val;
if( in->current_size == 0 )
return 0;
val = Queue_front(in);
in->current_size--;
in->front = (in->front+1) % in->max_size;
return val;
}
int Queue_front(Queue *in) {
if( in->current_size == 0 )
return 0;
return in->array[in->front];
}
The code starts with a structure definition, which has a pointer to the currently allocated array, an integer for the index of the front-most item, an integer for the back-most item, the number of elements in this array, and the maximum number of elements allowed in the array.
The enqueue() procedure will check to make sure that adding a new item won't overflow the array. It will then increment the "end" index, and wrap around to 0 if necessary.
The dequeue() function will return an arbitrary value (0 in this case) if we have underflowed. Else, it returns the oldest item in the list, and updates the "front" index, wrapping around to 0 if necessary.
The front() function will simply return the front-most item in the Queue.
Quiz
[edit | edit source]Assume that all data structures are 5 items long, and they can't resize:
1.) How would a Stack look at the end of this sequence of operations? What values would have been returned? Where is the index pointing?
push(14), push(42), pop(), top(), push(19), push(2), pop(), pop(), push(5), top()
2.) How would a Queue look at the end of this sequence of operations? What values would have been returned? Where are the indexes pointing?
enqueue(4), enqueue(8), dequeue(), enqueue(98), enqueue(15), dequeue(), dequeue(), enqueue(5), enqueue(2), top()
3.) Rewrite the Queue implementation so that it supports resizing itself.
Answers
[edit | edit source]Question 1:
| 14 | 5 | -- | -- | -- |
| ↑ | ||||
| Returned: 42, 14, 2, 19, 14 | ||||
Question 2:
| 2 | 8 | 98 | 15 | 5 |
| end | front | |||
| Returned: 4, 8, 98, 15 | ||||
Question 3:
Replace Queue_enqueue() with this:
void Queue_enqueue(Queue *in, int value) {
if( ++in->current_size > in->max_size ) {
int *temp;
unsigned int old_max, i, j;
old_max = in->max_size;
in->max_size *= 2;
temp = (int *) malloc( sizeof(int) * in->max_size );
for(i=in->end, j=0; j<old_max; i++, j++) {
if( i >= old_max )
i=0;
temp[j] = in->array[i];
}
free(in->array);
in->array = temp;
in->end = old_max;
in->front = 0;
}
in->array[in->end] = value;
in->end = (in->end+1) % in->max_size;
}