Data Structures. Stack

11 ноября 2023 г.

This is a short expanded summary of the section about stacks in the book Computer Science Guide by William Springer.

Basic information

A stack is a LIFO (Last In, First Out) data structure. Elements are added and removed only from the top. Stacks are useful for operations that require maintaining history.

A stack can be implemented using:

• an array (by tracking the current stack size) — but with a size limitation
• a singly linked list (by tracking the head and inserting/removing at the beginning) — no size limitation other than memory

Main operations (all O(1))

• push — add an element to the stack. If the stack is full (in a limited implementation), an overflow error occurs.
• pop — remove an element from the stack. If the stack is empty, an underflow error occurs.
• isEmpty — check whether the stack is empty
• size — get the number of elements in the stack
• peek — view the top element without removing it (equivalent to popping and pushing it back)

JavaScript implementation

In JavaScript, an array already functions as a stack, providing built-in methods such as push() and pop().

However, it is also interesting to implement a stack using a linked list.

This implementation is based on the example from that website. For my version, I use the linked list implementation that I introduced earlier.

1class Stack {
2	constructor() {
3	  this.linkedList = new LinkedList();
4	}
5	
6	isEmpty() {
7	  return !this.linkedList.head;
8	}
9	
10	peek() {
11	  if (this.isEmpty()) {
12		return null;
13	  }
14	  return this.linkedList.head.value;
15	}
16	
17	push(value) {
18	  this.linkedList.add(value);
19	}
20	
21	pop() {
22	  this.linkedList.remove();
23	}
24}

Example use case

A classic application of a stack is checking whether curly braces are balanced. Consider a language in which braces must always be properly matched: every closing brace (}) must have a corresponding opening brace ({) before it.

We can process the string one character at a time. Whenever we encounter an opening brace, we push it onto the stack. Whenever we encounter a closing brace, we pop an opening brace from the stack. If we attempt to pop from an empty stack, it means the closing brace has no matching opening brace. After processing the entire string, if the stack is not empty, there were more opening braces than closing braces. Otherwise, all braces in the string are correctly balanced.

I implemented this example in JavaScript as follows:

1function checkCurlyBrackets(string) {
2	let stack = [];
3	let message = ``;
4
5	for (let i = 0; i <= string.length - 1; i++) {
6		if (string[i] === "{") {
7			stack.push(string[i]);
8		}
9
10		if (string[i] === "}") {
11			if (stack.length === 0) {
12				return (message = "Unmatched closing brace.");
13			}
14
15			stack.pop();
16		}
17	}
18
19	if (stack.length > 0) {
20		message =
21			"The stack is not empty. There are more opening braces than closing braces in the string.";
22	} else {
23		message = "true";
24	}
25
26	return message;
27}
28
29const string1 = "This {} is a string {} with curly {} brackets:";
30const string2 = "This {} is a string } with curly {} brackets:";
31const string3 = "This {} is a string {} with curly { brackets:";
32
33console.log(checkCurlyBrackets(string1)); //true
34console.log(checkCurlyBrackets(string2)); // The closing brace does not have a matching opening brace.
35console.log(checkCurlyBrackets(string3)); // The stack is not empty. There are more opening braces than closing braces in the string.