<div id="readability-page-1" class="page"><div>
 <div id="SE-2633de63-eece-43ba-9e74-3ca7ac418b6c">
 안녕하세요 멍개입니다.​이번 시간에는 두 개의 스택을 이용하여 큐를 구현해보도록 하겠습니다.​먼저, 큐를 구현하기 전에 스택과 큐의 특징부터 간단히 살펴보겠습니다.​스택은, LIFO(Last In First Out) 특징을 가집니다. LIFO는 마지막에 들어온 데이터가 먼저 나간다는 의미입니다.큐는, FIFO(First In First Out) 특징을 가집니다. FIFO는 먼저 들어온 데이터가 먼저 나간다는 의미입니다.​기본적으로 스택에서는 데이터를 넣을땐 push, 뺄 땐 pop 메서드를 가집니다.큐에서는 데이터를 넣을땐 enqueue, 뺼 땐 dequeue 메서드를 가집니다.​· 스택 기반 큐 동작 방식스택 기반의 큐는 2개의 스택이 필요합니다.​첫 번째 스택은 enqueue될 때 push가 되는 스택입니다. (시간 복잡도: O(1)
 </div> <div id="SE-22530d09-aa52-4906-ac82-1c058818f03f">
 <a href="#" onclick="return false;" data-linktype="img" data-linkdata="{&quot;id&quot; : &quot;SE-22530d09-aa52-4906-ac82-1c058818f03f&quot;, &quot;src&quot; : &quot;https://mblogthumb-phinf.pstatic.net/MjAyNjA0MDFfMTg0/MDAxNzc0OTkzOTkwMzE2.65Ja84n_63Ualn1aRy1bBPZvFIExDED-UyIvcUrtXuAg.jwx6DFNXe6GmCA_B5jV4BtYPT3MOb2MymI4QbK-252og.PNG/%EC%8A%A4%ED%81%AC%EB%A6%B0%EC%83%B7_2026-04-01_%EC%98%A4%EC%A0%84_6.53.02.png&quot;, &quot;originalWidth&quot; : &quot;774&quot;, &quot;originalHeight&quot; : &quot;421&quot;, &quot;linkUse&quot; : &quot;false&quot;, &quot;link&quot; : &quot;&quot;, &quot;fileSize&quot;: &quot;41240&quot; }">
 <img src="https://mblogthumb-phinf.pstatic.net/MjAyNjA0MDFfMTg0/MDAxNzc0OTkzOTkwMzE2.65Ja84n_63Ualn1aRy1bBPZvFIExDED-UyIvcUrtXuAg.jwx6DFNXe6GmCA_B5jV4BtYPT3MOb2MymI4QbK-252og.PNG/%EC%8A%A4%ED%81%AC%EB%A6%B0%EC%83%B7_2026-04-01_%EC%98%A4%EC%A0%84_6.53.02.png?type=w800" data-width="693" data-height="376" alt="">
 </a>
 
 </div>
 <div id="SE-1671f0fb-edd0-4377-840e-baaa5d5ad80c">
 ​이제 dequeue가 일어나면 첫 번째 큐를 뒤집은 후 outbox로 넣습니다. 그리고 outbox에서 pop을 수행합니다.(시간 복잡도: O(n)
 </div> <div id="SE-db085a8a-3624-46ff-82fb-2c2c1c3807aa">
 <a href="#" onclick="return false;" data-linktype="img" data-linkdata="{&quot;id&quot; : &quot;SE-db085a8a-3624-46ff-82fb-2c2c1c3807aa&quot;, &quot;src&quot; : &quot;https://mblogthumb-phinf.pstatic.net/MjAyNjA0MDFfMTU4/MDAxNzc0OTk0MDc1NDgw.W5W8YrX3vSUd6sgiq7e8DRyI4-E4jeZOz4Xja4ycgK4g.X1BSXWfw04pbpiQ77ebXa7KhZk8IKh7qHMNn52aLzxYg.PNG/%EC%8A%A4%ED%81%AC%EB%A6%B0%EC%83%B7_2026-04-01_%EC%98%A4%EC%A0%84_6.54.16.png&quot;, &quot;originalWidth&quot; : &quot;367&quot;, &quot;originalHeight&quot; : &quot;268&quot;, &quot;linkUse&quot; : &quot;false&quot;, &quot;link&quot; : &quot;&quot;, &quot;fileSize&quot;: &quot;13813&quot; }">
 <img src="https://mblogthumb-phinf.pstatic.net/MjAyNjA0MDFfMTU4/MDAxNzc0OTk0MDc1NDgw.W5W8YrX3vSUd6sgiq7e8DRyI4-E4jeZOz4Xja4ycgK4g.X1BSXWfw04pbpiQ77ebXa7KhZk8IKh7qHMNn52aLzxYg.PNG/%EC%8A%A4%ED%81%AC%EB%A6%B0%EC%83%B7_2026-04-01_%EC%98%A4%EC%A0%84_6.54.16.png?type=w800" data-width="367" data-height="268" alt="">
 </a>
 
 </div>
 <div id="SE-22d6b2d5-d8a2-459c-843e-6eee8e2e1834">
 enqueue가 호출되면 inbox stack에서 push를 호출합니다. (시간 복잡도: O(1)
 </div> <div id="SE-0e1095ff-868c-45b6-ad21-ff286344fac4">
 <a href="#" onclick="return false;" data-linktype="img" data-linkdata="{&quot;id&quot; : &quot;SE-0e1095ff-868c-45b6-ad21-ff286344fac4&quot;, &quot;src&quot; : &quot;https://mblogthumb-phinf.pstatic.net/MjAyNjA0MDFfMjI5/MDAxNzc0OTk0MTE4MzYz.LL83-18jL8HN6NUA-mhiJLGCYhqxGbGFggbMnvjP51cg.bOcskCtu0PmULaTM3ClF6lAwua9RSsEpHm3srMAyCQcg.PNG/%EC%8A%A4%ED%81%AC%EB%A6%B0%EC%83%B7_2026-04-01_%EC%98%A4%EC%A0%84_6.55.10.png&quot;, &quot;originalWidth&quot; : &quot;361&quot;, &quot;originalHeight&quot; : &quot;271&quot;, &quot;linkUse&quot; : &quot;false&quot;, &quot;link&quot; : &quot;&quot;, &quot;fileSize&quot;: &quot;13597&quot; }">
 <img src="https://mblogthumb-phinf.pstatic.net/MjAyNjA0MDFfMjI5/MDAxNzc0OTk0MTE4MzYz.LL83-18jL8HN6NUA-mhiJLGCYhqxGbGFggbMnvjP51cg.bOcskCtu0PmULaTM3ClF6lAwua9RSsEpHm3srMAyCQcg.PNG/%EC%8A%A4%ED%81%AC%EB%A6%B0%EC%83%B7_2026-04-01_%EC%98%A4%EC%A0%84_6.55.10.png?type=w800" data-width="361" data-height="271" alt="">
 </a>
 
 </div>
 <div id="SE-110d28ef-fcfc-4083-98ec-abda2a30c35a">
 dequeue가 호출되면 outbox stack에서 pop을 호출합니다. (시간 복잡도: O(1)
 </div> <div id="SE-f3cb5ca4-15a5-4c5a-bb20-6b74cf916e1c">
 <a href="#" onclick="return false;" data-linktype="img" data-linkdata="{&quot;id&quot; : &quot;SE-f3cb5ca4-15a5-4c5a-bb20-6b74cf916e1c&quot;, &quot;src&quot; : &quot;https://mblogthumb-phinf.pstatic.net/MjAyNjA0MDFfMTc0/MDAxNzc0OTk0MTc3MjE1.PpX1owHY46310qsMqdbu5iirTcz320nLAXDyFKjWrrcg.-4p3IWFJYhHzct6avtKfOwzdrGWdL1XtWscAdr8oM2Ig.PNG/%EC%8A%A4%ED%81%AC%EB%A6%B0%EC%83%B7_2026-04-01_%EC%98%A4%EC%A0%84_6.56.09.png&quot;, &quot;originalWidth&quot; : &quot;377&quot;, &quot;originalHeight&quot; : &quot;269&quot;, &quot;linkUse&quot; : &quot;false&quot;, &quot;link&quot; : &quot;&quot;, &quot;fileSize&quot;: &quot;13185&quot; }">
 <img src="https://mblogthumb-phinf.pstatic.net/MjAyNjA0MDFfMTc0/MDAxNzc0OTk0MTc3MjE1.PpX1owHY46310qsMqdbu5iirTcz320nLAXDyFKjWrrcg.-4p3IWFJYhHzct6avtKfOwzdrGWdL1XtWscAdr8oM2Ig.PNG/%EC%8A%A4%ED%81%AC%EB%A6%B0%EC%83%B7_2026-04-01_%EC%98%A4%EC%A0%84_6.56.09.png?type=w800" data-width="377" data-height="269" alt="">
 </a>
 
 </div>
 <div id="SE-c1a50fd0-10b2-4742-b068-02eda0f9444c">
 dequeue가 호출되면 outbox stack에서 pop을 호출합니다. (시간 복잡도: O(1)
 </div> <div id="SE-228f77eb-274d-4b45-b18a-abc219fd3fbf">
 <a href="#" onclick="return false;" data-linktype="img" data-linkdata="{&quot;id&quot; : &quot;SE-228f77eb-274d-4b45-b18a-abc219fd3fbf&quot;, &quot;src&quot; : &quot;https://mblogthumb-phinf.pstatic.net/MjAyNjA0MDFfMTk3/MDAxNzc0OTk0MjQ0NTk2.7NSr2ITWNI-krgvvN3LNyAmYKJ-ovTPDwvpSqSpjgbQg.ofmS3RAYM5EvgI_vqGDbhopXUPofyuRUacNZIl1OFDkg.PNG/%EC%8A%A4%ED%81%AC%EB%A6%B0%EC%83%B7_2026-04-01_%EC%98%A4%EC%A0%84_6.57.21.png&quot;, &quot;originalWidth&quot; : &quot;373&quot;, &quot;originalHeight&quot; : &quot;268&quot;, &quot;linkUse&quot; : &quot;false&quot;, &quot;link&quot; : &quot;&quot;, &quot;fileSize&quot;: &quot;13284&quot; }">
 <img src="https://mblogthumb-phinf.pstatic.net/MjAyNjA0MDFfMTk3/MDAxNzc0OTk0MjQ0NTk2.7NSr2ITWNI-krgvvN3LNyAmYKJ-ovTPDwvpSqSpjgbQg.ofmS3RAYM5EvgI_vqGDbhopXUPofyuRUacNZIl1OFDkg.PNG/%EC%8A%A4%ED%81%AC%EB%A6%B0%EC%83%B7_2026-04-01_%EC%98%A4%EC%A0%84_6.57.21.png?type=w800" data-width="373" data-height="268" alt="">
 </a>
 
 </div>
 <div id="SE-1c44cc2c-6e20-4fb0-beb6-108e3e5dbfdd">
 또 dequeue가 호출되면 inbox stack에서 하나씩 pop하여 outbox stack에 push합니다. (시간 복잡도: O(n)​즉, outbox가 비어있을때만 Inbox stack에 쌓여있는 데이터를 pop하여 outbox stack에 push합니다. outbox stack이 비어있지 않다면 pop으로 바로 데이터를 뺄 수 있습니다.​이렇듯 두 개의 스택을 이용하여 큐를 구현하면 dequeue가 평균적으로 O(1) 시간복잡도를 가지며 이를 amortized O(1) 이라고 합니다.​· 코드 구현타입스크립트와 파이썬과 같은 언어에서는 이미 기본 자료구조로 제공하는 리스트가 스택과 동일한(or 유사한) 형태로 구현이 되어 있어 간단하게 구현할 수 있습니다.
 </div> <div id="SE-04d92b0f-e1bd-47ec-a625-af4a8cb3bdb8">
 class QueueWithTwoStacks&lt;T&gt; {
 private inbox: T[] = []; // enqueue용
 private outbox: T[] = []; // dequeue용

 enqueue(val: T): void {
 this.inbox.push(val); // 항상 O(1)
 }

 dequeue(): T | undefined {
 if (this.outbox.length === 0) {
 // inbox → outbox 전체 이동 (순서가 역전 → 큐 순서 복원)
 while (this.inbox.length &gt; 0) {
 this.outbox.push(this.inbox.pop()!);
 }
 }
 return this.outbox.pop();
 }

 peek(): T | undefined {
 if (this.outbox.length === 0) {
 while (this.inbox.length &gt; 0) {
 this.outbox.push(this.inbox.pop()!);
 }
 }
 return this.outbox[this.outbox.length - 1];
 }

 get size(): number {
 return this.inbox.length + this.outbox.length;
 }
}
 </div> <div id="SE-57eb2fe3-276d-4e4e-b95a-948d602c6072">
 ​· 왜 굳이?마지막으로 생각해 볼 문제는 왜 굳이 이런 자료구조를 사용할까 입니다. ​그냥 큐 쓰면 안돼??? 큐의 dequeue는 시간복잡도를 확정적 O(1)을 가지는데????​스택으로 구현된 큐와 일반큐의 가장 큰 차이점이 무엇일까요?​그것은 바로 enqueue와 dequeue의 대상입니다. ​일반적인 큐는 enqueue 또는 dequeue가 수행되는동안 반대의 작업을 수행할 수 없습니다. 하지만 스택으로 구현된 큐는 enqueue 또는 dequeue가 수행되는 동안 반대 작업을 수행할 수 있습니다. 단, dequeue가 수행될 때 outbox stack이 비어서 enqueue의 데이터를 dequeue로 이동할 때는 enqueue 또는 dequeue가 수행될 수 없습니다. 즉, 동시성 또는 병렬 처리에 유리한 점이 있습니다. ​즉, 생산자/소비자를 물리적으로 분리하여 경합을 최소화할 수 있습니다.
 </div> <div id="SE-a4a9f8cd-9592-464c-8bac-6a7bef00b7f6">
 // acquireLock / releaseLock은 Mutex 구현체로 대체
// Node.js 환경에서는 Atomics + SharedArrayBuffer,
// 또는 async-mutex 라이브러리 활용

class ConcurrentTwoStackQueue&lt;T&gt; {
 private inbox: T[] = [];
 private outbox: T[] = [];
 private inboxLock = false;
 private outboxLock = false;

 enqueue(val: T): void {
 // inbox lock만 잡으면 됨
 // dequeue가 outbox에서 작업 중이어도 무관
 acquireLock('inbox');
 this.inbox.push(val);
 releaseLock('inbox');
 }

 dequeue(): T | undefined {
 acquireLock('outbox');

 if (this.outbox.length === 0) {
 // 이 순간만 inbox lock도 추가로 필요
 acquireLock('inbox');
 while (this.inbox.length &gt; 0) {
 this.outbox.push(this.inbox.pop()!);
 }
 releaseLock('inbox');
 }

 const val = this.outbox.pop();
 releaseLock('outbox');
 return val;
 }
}
 </div> <div id="SE-32da242c-0c80-4d67-8be9-c6d37cd5cee9">
 ​​또... 그럴일은 없지만 스택만 존재하는 케이스?​​
 </div> </div></div>

삽질하는 멍개씨

안녕하세요 멍개입니다. 이번 시간에는 두 개의 스택을 이용하여 큐를 구현해보도록 하겠습니다. 먼저, 큐를 구현하기 전에 스택과 큐의 특징부터 간단히 살펴보겠습니다. 스택은, LIFO(Last In First Out) 특징을 가집니다. LIFO는 마지막에 들어온 데이터가 먼저 나간다는 의미입니다. 큐는, FIFO(First In First Out) 특징을 가집니다. FIFO는 먼저 들어온 데이터가 먼저 나간다는 의미입니다. 기본적으로 스택에서는 데이터를 넣을땐 push, 뺄 땐 pop 메서드를 가집니다. 큐에서는 데이터를 넣을땐 enqueue, 뺼 땐 dequeue 메서드를 가집니다. · 스택 기반 큐 동작 방식 스택 기반의 큐는 2개의 스택이 필요합니다. 첫 번째 스택은 enqueue될.......

[알고리즘] 두 개의 스택으로 큐 구현하기

댓글