This post is part of a personal study group activity, summarizing the content after reading through the book "Grokking Algorithms."

This chapter covers stacks and queues. In fact, both of these data structures are essentially arrays with specific constraints applied. You might think this concept of a "constraint" would only be useful in special situations, but on the contrary, the very rules imposed by these constraints make them useful in a huge number of places.

The defining feature of stacks and queues is that data processing has an inherent order. According to their respective constraints, stacks and queues always process data in a fixed order. Thanks to this property, they're extremely useful for tasks that require ordering. Common examples include schedulers and waiting queues, and OS interrupt handling relies on a stack.

The way a stack manages data is very similar to that of an array. As mentioned above, stacks and queues have specific constraints, and a stack's constraints are as follows.

• Data can only be inserted at the stack's entrance.
• Only the data at the very end of the stack can be read.
• Only the data at the very end of the stack can be deleted.

A stack has only one entrance, and all operations happen at this entrance. It helps to picture a tall can of Pringles. To eat a Pringles chip, you have no choice but to take it out through the fixed opening, and only the chip on top can be removed. Mapping the stack's data and operations onto this image works remarkably well.

The stack's entrance—that is, the end—is called the top, and the very bottom of the stack is called the bottom. A stack's operations fall into two categories.

Here's a diagram of the stack's push operation.

1. Push 2 onto the stack.

2. Push 6 onto the stack.

3. Push 9 onto the stack.

Remember that a push always happens at the top of the stack.

Here's the stack's pop operation.

1. Pop 9 from the stack.

2. Pop 6 from the stack.

After this process, only 5 remains in the stack. Since a stack only ever allows inserting data at the top, inserting data in the middle of the stack requires popping every element down to that position first, then pushing back.

This pattern—where the first thing in is the last thing out, and conversely, the last thing in is the first thing out—is called LIFO (Last In, First Out).

Think about your commute on a Monday morning. Wouldn't you want to get in as late as possible and get out as early as possible?

I tend to be quite particular about code style. I'm needlessly sensitive about it, to the point where just reading source code that isn't formatted my way stresses me out. It would be more tolerable if it at least followed some consistent set of rules even if it's not my style, but seeing code written with no consistency at all is really something else... On top of already struggling to read code properly, if the code is also messy, it feels pretty hopeless.

That's why I'm a huge fan of ESLint. It tells me whether TypeScript, HTML, and other code conforms to the rules I've defined, and even fixes the parts that don't. For someone as particular about code style as me, it's practically a necessity.

A Lint tool that formats code like this needs to understand each language's different rules individually and accurately spot the parts that violate them, so at first glance it looks very difficult to implement. In this section, we'll use a stack to build a simple code Lint.

For example, let's assume we have code like this.

JAVASCRIPT
// 정상
const list1 = [ 1, 2, 3 ]

// 오류1. 닫는 대괄호 없음
const list2 = [ 1, 2, 3

// 오류2. 여는 대괄호 없음
const list3 = 1, 2, 3]

// 오류3. 괄호 쌍이 맞지 않음
const list4 = (1, 2, 3]

In every language, brackets always come in pairs. Accordingly, every line except list1 will be flagged with an error. Using a stack doesn't automatically make implementing a linter easy. Designing a fully functional linter is very difficult, so here we'll only think about brackets.

The bracket-lint rules defined in the book are as follows.

1. Ignore every character that isn't a bracket.
2. When an opening bracket appears, push it onto the stack. Putting it on the stack means waiting for that bracket to be closed.
3. When a closing bracket appears, check the element on top of the stack and analyze as follows.
   • If there's no element on the stack, that means no opening bracket appeared beforehand—this is Error 2.
   • If there's data on the stack, but the closing bracket doesn't match the type of the element on top of the stack, this is Error 3.
   • If the closing bracket matches the type of the element on top of the stack, the bracket has been successfully closed, which is a normal case. Since that bracket no longer needs tracking, POP the element off the top of the stack.
4. If the end of the line is reached while elements remain on the stack, that means there's a missing closing bracket—Error 1.

Applying the defined rules to an example gives us the following.

The example is based on the statement shown above, and the stack is illustrated as shown.

1. Push the opening parenthesis onto the stack.

If this had been a closing bracket instead, it would have been an error.

2. Move the pointer forward until the next bracket appears.

Non-bracket tokens like var and x are all ignored. From here on, step 2's description will be omitted.

3. Push the opening curly brace onto the stack.

Even though its type differs from the bracket beneath it on the stack, both are opening brackets, so as long as each closes properly, there's no error.

4. Push the opening square bracket onto the stack.

Likewise, push it onto the stack.

5. A closing square bracket is detected, so compare it against the top element of the stack and pop.

A pop operation is valid when the following conditions hold.

• The bracket on top of the stack matches the type of bracket at the current pointer.
• The bracket on top of the stack must be an opening bracket.

Since both conditions are met in this case, the opening square bracket is popped off the stack and removed.

6. A closing curly brace is detected, so compare it against the top element of the stack and pop.

Since the opening square bracket was already removed from the stack by the previous pop, the current top of the stack is now the opening curly brace. The conditions are met, so it's likewise popped off and removed.

7. A closing parenthesis is detected, so compare it against the top element of the stack and pop.

Likewise, since the conditions are met, the element is popped.

8. Having reached the end of the code, check the state of the stack to determine whether there's an error.

We've now checked every element in the code. If even a single element remains on the stack, that means an error occurred in the statement.

In this case, since the stack has no elements left, we can determine that the statement is valid. That is, the linter we've designed reports no errors for the statement above.

JAVA
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;

/**
 * 누구나 자료 구조와 알고리즘 괄호 린트 클래스
 *
 * @author RWB
 * @see <a href="https://blog.itcode.dev/posts/2021/07/31/about-algorithm-chapter08/">스택과 큐로 간결한 코드 생성</a>
 * @since 2021.07.30 Fri 23:30:56
 */
public class Linter
{
	/**
	 * 메인 함수
	 *
	 * @param args: [String[]] 매개변수
	 *
	 * @throws IOException 데이터 입출력 예외
	 */
	public static void main(String[] args) throws IOException
	{
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
		
		writer.write("후보 이름 입력 (x: 종료) >> ");
		writer.flush();
		
		String code = reader.readLine();
		
		char c = lint(code);
		
		// 린트 결과가 정상일 경우
		if (c == '0')
		{
			writer.write("오류 없음");
		}
		
		// 여는 괄호가 없을 경우
		else if (c == 'x')
		{
			writer.write("여는 괄호 존재하지 않음");
		}
		
		// 닫는 괄호가 없을 경우
		else
		{
			writer.write(c);
			writer.write(" 닫는 괄호 존재하지 않음");
		}
		
		writer.newLine();
		writer.flush();
		
		writer.close();
		reader.close();
	}
	
	/**
	 * 린트 결과 반환 함수
	 *
	 * @param text: [String] 구문
	 *
	 * @return [char] 린트 결과
	 */
	private static char lint(String text)
	{
		Stack<Character> stack = new Stack<>();
		
		for (int i = 0; i < text.length(); i++)
		{
			char c = text.charAt(i);
			
			// 여는 괄호일 경우
			if (isOpenBrace(c))
			{
				stack.push(c);
			}
			
			// 닫는 괄호일 경우
			else if (isCloseBrace(c))
			{
				// 스택이 비어있을 경우
				if (stack.isEmpty())
				{
					return 'x';
				}
				
				// 스택이 비어있지 않을 경우
				else
				{
					char co = stack.pop();
					
					// 괄호가 서로 매칭되지 않을 경우
					if (!isMatched(co, c))
					{
						return co;
					}
				}
			}
		}
		
		// 스택이 비어이쓸 경우
		if (stack.isEmpty())
		{
			return '0';
		}
		
		// 스택이 비어있지 않을 경우
		else
		{
			return stack.pop();
		}
	}
	
	/**
	 * 여는 괄호 여부 반환 함수
	 *
	 * @param c: [char] 문자
	 *
	 * @return [boolean] 여는 괄호 여부
	 */
	private static boolean isOpenBrace(char c)
	{
		return c == '(' || c == '{' || c == '[';
	}
	
	/**
	 * 닫는 괄호 여부 반환 함수
	 *
	 * @param c: [char] 문자
	 *
	 * @return [boolean] 여는 괄호 여부
	 */
	private static boolean isCloseBrace(char c)
	{
		return c == ')' || c == '}' || c == ']';
	}
	
	/**
	 * 괄호 매칭 여부 반환 함수
	 *
	 * @param open: [char] 여는 괄호
	 * @param close: [char] 닫는 괄호
	 *
	 * @return [boolean] 괄호 매칭 여부
	 */
	private static boolean isMatched(char open, char close)
	{
		// 소괄호가 서로 매칭될 경우
		if (open == '(' && close == ')')
		{
			return true;
		}
		
		// 중괄호가 서로 매칭될 경우
		else if (open == '{' && close == '}')
		{
			return true;
		}
		
		// 아닐 경우
		else
		{
			return open == '[' && close == ']';
		}
	}
}

INPUT
const a = (1 + 2 * 3;

OUTPUT
( 닫는 괄호 존재하지 않음

The source code and input/output are as shown above. It analyzes the string character by character, and when an opening bracket is detected, it's pushed onto the stack.

If a closing bracket appears during analysis, the stack is popped and compared against the closing bracket to check whether the types match. If they match, processing continues; if not, the corresponding error is reported.

JAVA
for (int i = 0; i < text.length(); i++)
{
	char c = text.charAt(i);
	
	// 여는 괄호일 경우
	if (isOpenBrace(c))
	{
		stack.push(c);
	}
	
	// 닫는 괄호일 경우
	else if (isCloseBrace(c))
	{
		// 스택이 비어있을 경우
		if (stack.isEmpty())
		{
			return 'x';
		}
		
		// 스택이 비어있지 않을 경우
		else
		{
			char co = stack.pop();
			
			// 괄호가 서로 매칭되지 않을 경우
			if (!isMatched(co, c))
			{
				return co;
			}
		}
	}
}

This behavior is controlled by the source code above. Also, if any elements remain on the stack after all processing is finished, that means there's a bracket that was never properly closed, so an error is reported in that case as well.

JAVA
// 스택이 비어있을 경우
if (stack.isEmpty())
{
	return '0';
}

// 스택이 비어있지 않을 경우
else
{
	return stack.pop();
}

This behavior is controlled by the source code above, after all detection has finished.

As shown here, stacks are extremely useful whenever the most recently entered data needs to be processed first. This applies to linting, as we just saw, as well as things like Ctrl + Z, which saves us from our own mistakes.

A queue, similarly to a stack, is also a data structure built by applying specific rules to an array. A queue's constraints are as follows.

• Data can only be inserted at the end of the queue. (same as a stack)
• Data can only be read from the front of the queue. (opposite of a stack)
• Data can only be deleted from the front of the queue. (opposite of a stack)

The core idea is similar to a stack, but the operations differ slightly. Where a stack has a single unified entrance and exit, a queue has separate entrances and exits. It helps to picture a stack as a can of Pringles, and a queue as an ordinary pipe. Except this pipe only flows in one direction.

Unlike a stack, a queue doesn't have a dedicated operation name like PUSH. Here's a diagram of a queue's operations.

1. Insert 8 into the queue.

2. Insert 93 into the queue.

3. Insert 51 into the queue.

So far, this isn't much different from a stack's PUSH operation.

4. Remove 8 from the queue.

Unlike a stack, a queue removes data from the opposite end from where data is inserted.

5. Remove 93 from the queue.

6. Remove 51 from the queue.

You can see how it processes elements sequentially, much like a conveyor belt.

Thanks to the queue's property of processing data sequentially in a way different from a stack, it's put to good use in all kinds of places. Waiting lines, job scheduling, and similar tasks operate on FIFO (First In, First Out), where the first element in is the first one out.

JAVA
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Objects;
import java.util.Queue;

/**
 * 누구나 자료 구조와 알고리즘 큐 프린터 클래스
 *
 * @author RWB
 * @see <a href="https://blog.itcode.dev/posts/2021/07/31/about-algorithm-chapter08/">스택과 큐로 간결한 코드 생성</a>
 * @since 2021.07.31 Sat 03:21:35
 */
public class Printer
{
	/**
	 * 메인 함수
	 *
	 * @param args: [String[]] 매개변수
	 *
	 * @throws IOException 데이터 입출력 예외
	 */
	public static void main(String[] args) throws IOException
	{
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
		
		Queue<String> queue = new LinkedList<>();
		
		while (true)
		{
			writer.write("출력할 문자열 입력 (x: 종료) >> ");
			writer.flush();
			
			String work = reader.readLine();
			
			// 입력을 종료할 경우
			if (work.equalsIgnoreCase("x"))
			{
				break;
			}
			
			// 작업할 입력이 들어올 경우
			else
			{
				queue.offer(work);
			}
		}
		
		while (!queue.isEmpty())
		{
			writer.write("[INFO] ");
			writer.write(Objects.requireNonNull(queue.poll()));
			writer.newLine();
			writer.flush();
		}
		
		writer.close();
		reader.close();
	}
}

INPUT
First Document
Second Document
Third Document
Fourth Document
Fifth Document
x

OUTPUT
[INFO] First Document
[INFO] Second Document
[INFO] Third Document
[INFO] Fourth Document
[INFO] Fifth Document

At a glance, this might look like it's just printing the input straight to the console in the order it was entered, but that's simply because this source is so simple.

In practice, when doing more complex work, you often need to save tasks under certain conditions and then process them sequentially afterward. In situations like this, a queue's properties are extremely useful.

You might argue that you could just as well use a familiar array, but if tasks are frequently being added and removed, you have to carefully manage the array's indices. A queue, on the other hand, has fixed rules for how data flows in and out, so you can add and remove items without worrying about indices at all.

The key points of this chapter can be summarized as follows.

• A stack follows Last In, First Out (LIFO).
• Both adding and removing elements in a stack happen at the top of the stack.
• Inserting an element in the middle of a stack requires removing every element down to that position first.
• A queue follows First In, First Out (FIFO).
• A queue adds elements on one side and removes them on the other, each independently.

The concepts of stacks and queues themselves weren't difficult, but I wasn't very familiar with working with them in Java. Writing up this chapter let me learn not just the properties of stacks and queues, but also how to work with them in Java.

The next chapter covers recursion, a technique that's extremely effective at shortening repetitive operations.