The Stack Data Structure
Mugurel Ionu Andreica
Spring 2012
Operations
push(x)
Adds the element x at the top of the stack
pop()
Removes the element from the top of the stack and returns it
Returns an error if the stack is empty
peek()
Returns (but does not remove) the element at the top of the
stack
isEmpty()
Returns 1 if the stack is empty and 0 otherwise
The axioms are given implicitly they determine the
expected behavior of the stack for a given sequence of
operations
See the examples on the upcoming slides
Stack - Example
pop()
returns 13
push(13)
push(7)
13
pop()
peek()
returns 10 returns 10
peek()
returns 20
push(10)
10
10
10
10
pop()
returns 3
push(3)
push(20)
20
Stack Array-based
Implementation
#include <stdio.h>
T peek() {
if (isEmpty()) {
fprintf(stderr, "Error 103 - The stack is empty!\n");
T x;
return x;
}
return stackArray[topLevel]; }
#define NMAX 100
template<typename T> class Stack {
private:
T stackArray[NMAX];
int topLevel;
public:
void push(T x) {
if (topLevel >= NMAX - 1) {
fprintf(stderr, "Error 101 - The stack is full!\n");
return;
}
topLevel++;
stackArray[topLevel] = x;
}
T pop() {
if (isEmpty()) {
fprintf(stderr, "Error 102 - The stack is empty!\n");
T x;
return x;
}
T x = stackArray[topLevel];
topLevel--;
return x;
}
int isEmpty() {
return (topLevel < 0); }
Stack() { // constructor
topLevel = -1; } // the stack is empty in the beginning
};
int main() {
Stack<int> s;
[Link](7); [Link](3); [Link](10); [Link](13); [Link](20);
[Link](9); [Link](1); printf("%d\n", [Link]());
printf("%d\n", [Link]()); printf("%d\n", [Link]());
printf("%d\n", [Link]()); printf("%d\n", [Link]());
[Link](100); printf("%d\n", [Link]());
return 0;
}
Paranthesis Checking
Given a string S composed of the characters (,
), [, ], {, } (round bracket, square bracket and
curly bracket), determine if the parantheses are
correctly balanced
S=([()[{([]()){}}[[]]]{}])[]({}) is correctly balanced
S1=([]({)}), S2=[{{}(())([]{, S3=[(){}]] are not
correctly balanced
Algorithm
We use a stack
We traverse the string from left to right
We push on the stack every open bracket
For every closed bracket, the bracket at the top of the stack
must be an open bracket of the same type (and the stack must
not be empty) => then we pop the open bracket from the stack
In the end, the stack must be empty
Paranthesis Checking Implementation
#include <stdio.h>
#include <string.h>
fprintf(stderr, "Error 202 - Wrong paranthesis\n");
error = 1;
break;
// copy & paste the definition of the Stack class
}
char s[200]="([{()[]}(()[{}()])])(){}[{{()[]}()}]";
int error = 0;
int main() {
Stack<char> stk;
[Link]();
}
}
for (int i = 0; i < strlen(s); i++) {
if (!error && ![Link]())
if (s[i] == '(' || s[i] == '[' || s[i] == '{')
fprintf(stderr, "Error 203 - The stack is not empty at the
[Link](s[i]);
end\n");
else if ([Link]()) {
else if (!error)
fprintf(stderr, "Error 201 - Empty stack\n");
printf("OK\n");
error = 1;
break;
}
return 0;
else {
}
if ((s[i] == ')' && [Link]() != '(') ||
(s[i] == ']' && [Link]() != '[') ||
(s[i] == '}' && [Link]() != '{')) {
Header with the Stack Class
Definition
Definition of the Stack class must be copy-pasted in
every program in which it is used => annoying +
prone to mistakes (maybe we do not copy-paste
everything, or we copy-paste more than we need)
Elegant solution: define the Stack class in a header
file (e.g. mystack.h)
Any program that uses the Stack class will include
the header file
#include mystack.h (or #include <mystack.h>)
we will proceed similarly for the upcoming data structures